/**
 * Heap
 */

public class Heap
{

    /**
     * public static boolean isHeap(int[] a, int heapsize)
     *
     * precondition: a != null
     *               a.length() >= heapsize
     * 
     * The function returns true if and only if the binary tree rooted at a[0]
     * satisfies the heap property or heapsize==0.
     *   
     */
    public static boolean isHeap(int[] a, int heapsize) 
    {
        boolean flag = true;
        
        for (int i = parent(heapsize); i > -1; i--){
        	if (((left(i) > heapsize - 1) || (a[left(i)] >= a[i])) &&
        			((right(i) > heapsize - 1) || (a[right(i)] >= a[i])))
        		flag = true;
        	else {
        		flag = false;
        		break;
        	}
        }
//        for (int val :  a)
//        	System.out.print(val + ",");
        return flag;
    }


    /**
     * public static int parent(i), left(i), right(i)
     * (3 methods)
     *
     * precondition: i >= 0
     *
     * The methods compute the index of the parent and right and left
     * childred of vertex i in a complete binary tree stored in an array.
     * Note that indices of arrays in Java start from 0.
     */
    public static int parent(int i) { return (int) Math.floor((i - 1) / 2);} // just for illustration - should be replaced by student code
    public static int left  (int i) { return (2 * i) + 1;} // just for illustration - should be replaced by student code
    public static int right (int i) { return (2 * i) + 2;} // just for illustration - should be replaced by student code

    /**
    * public static void Insert(int[] a, int heapsize, int value)
    *
    * precondition: a != null
    *               a.length() >= heapsize+1
    *               value >= 0
    *               isHeap(a, heapsize)
    * 
    * postcondition: isHeap(a, heapsize+1)
    */
    public static void Insert(int[] a, int heapsize, int value) 
    {        
    	/*first - check if the array has at least 2 free cells
    	 * if not - double the array size
    	 */
    	if ((a.length - heapsize) == 1){
    		int[] tempHeap = new int[2 * a.length];
    		
    		/*copy elements from the original array
    		 to the temp. array */
    		for (int i = 0; i < a.length - 1; i++){
    			tempHeap[i] = a[i];
    		}
    		/*switch heap reference to the new heap array*/ 
    		a = tempHeap;
    	}
    	
    	/*add the new value in the end of the array
    	 * increment heapSize
    	 * and fix violations with heapify()
    	 */
    	a[heapsize] = value;
    	heapsize++;
    	heapifyUp(a, heapsize - 1);
    }

    /**
    * public static void Delete_Min(int[] a, int heapsize)
    *
    * precondition: a != null
    *               a.length() >= heapsize
    *               heapsize >= 1
    *               isHeap(a, heapsize)
    * 
    * postcondition: isHeap(a, heapsize-1)
    */
    public static void Delete_Min(int[] a, int heapsize)
    {
     	a[0] = a[heapsize - 1];
     	heapsize--;
     	heapifyDown(a, 0, heapsize);
    }


    /**
     * public static void Get_Min()(int[] a, int heapsize)
     *
     * precondition: a != null
     *               a.length() >= heapsize
     *               heapsize >= 1
     *               isHeap(a, heapsize)
     * 
     * postcondition: isHeap(a, heapsize)
     */
    public static int Get_Min(int[] a, int heapsize)
    {
    	/*might be a problem with nullPointerException
    	 * if the tester violates contract*/
    	if (heapsize > 0) return a[0];
    	else return Integer.MIN_VALUE;
    }  
    
    /*almost identical to the LCRS algorithm*/
    private static void heapifyDown(int[] a, int i, int heapSize){
    	int left = left(i);
    	int right = right(i);
    	int smallest = i;
    	int temp = 0;
    	
    	if (left < heapSize && a[left] < a[i])
    		smallest = left;
    	
    	if (right < heapSize && a[right] < a[smallest])
    		smallest = right;
    	
    	if (smallest > i){
    		temp = a[i];
    		a[i] = a[smallest];
    		a[smallest] = temp;
    		heapifyDown(a, smallest, heapSize);
    	}
    }
    
    private static void heapifyUp(int[] a, int i){
    	int temp = -1;
    	
    	while (i > 0 && a[i] < a[parent(i)]){
    		temp = a[parent(i)];
    		a[parent(i)] = a[i];
    		a[i] = temp;
    		i = parent(i);
    	}
    }
}
